This invention relates to a signal processing device and a signal processing method for performing forward transform computations and inverse transform computations of so-called improved discrete cosine transform (or modified DCT) at high speed for the purpose of realizing a linear transform of various digital signals such as audio signals and video signals and also for performing a code string transform from a coding system into another at high speed.
The orthogonal transform coding is known as a high efficiency coding technique adapted to high efficiency bit compression of a signal comprising time series sample data such as audio signal. With this transform coding technique, the input signal is subjected to an orthogonal transform coding operation on a block by block basis. The discrete cosine transform (DCT) is a typical orthogonal transformation. However, this transform technique is accompanied by the problem of block distortion that the discontinued boundary of adjacent blocks is perceived as noise. Therefore, adjacent blocks are normally made to overlap each other at the related ends.
The MDCT (modified DCT) is a technique for making the front and rear halves of each block of sample data overlap respectively the rear half of the preceding block and the front half of the succeeding block but not transmitting the samples of overlapped areas in duplicate. Therefore, it is highly suited to high efficiency coding operations.
The MDCT and the IMDCT (inverse MDCT) are described in a number of papers including Mochizuki, Yano and Nishitani, “The Restricting Conditions for Filters for the MDCT using a Mixture of a Plurality of Block Sizes” (Bulletin of Science & Technology of Telecommunication, CAS90-10, DSP90-14, pp. 66-60) and Uzu, Sugiyama, Iwadare and Nishitani, “The Adaptive Transform Coding with Adaptive Block Lengths Using the MDCT (ATC-ABS)” (The Papers for the Speeches in the 1999 Spring National Conference of the Society of Electronic Information and Telecommunication, A-197). They will be briefly described below by referring to FIG. 1 of the accompanying drawing.
Referring to FIG. 1, any block, for instance the J-th block, of the input time series sample data overlaps the rear half (50%) of the (J−1)-th block and the front half (50%) of the (J+1)-th block. If the number of samples of the J-th block is N (natural number), it overlaps the (J−1)-th block by N/2 samples.
For instance, a preprocessing filter or a window for forward transform Wh is provided for the input time series samples 101 of the J-th block to reduce them into N time series data 102. The preprocessing filter or the forward transform window Wh is so selected as to maximize the power concentration of the transformed data in response to the statistic properties of the input signal.
Then, the time series data 102 for the N samples are subjected to a linear forward transform processing operation of MDCT to produce N/2 independent spectrum data 103 on the frequency axis, the number of which data is a half of that of the input samples.
Then, the N/2 spectrum data 103 are subjected to a linear inverse transform processing operation of IMDCT to become N time series data 104.
Then, a synthetic filter or a window for inverse transform Wh is provided for the time series data 104 to produce time series data 105, which is added to the output of the preceding block and that of the succeeding block to restore the original input time series sample data 105.
As for specific methods of performing arithmetic operations of MDCT or IMDCT, Japanese Patent Application Laid-Open No. 5-183442 filed by the applicant of this patent application proposes an MDCT method to be used for an input signal of N samples to obtain an output of N/2 spectrums by carrying out preprocessing and postprocessing operations on the input signal and performing an FFT (fast Fourier Transform) on the basis of N/4 samples and an IMDCT method to be used for an input signal of N/2 spectrum data to obtain an output of N samples by carrying out preprocessing and postprocessing operations on the input signal and performing an FFT on N/2 spectrums on the basis of a tap length corresponding to N/4 spectrums.
Now, the methods described in Japanese Patent Application Laid-Open No. 5-183442 will be summarily described below.
The defining equation of MDCT is given by formula (1) below.
                                                        y              0                        ⁡                          (              k              )                                =                                    C              0                        ⁢                                          ∑                                  n                  =                  0                                                  N                  -                  1                                            ⁢                                                                    x                    0                                    ⁡                                      (                    n                    )                                                  ⁢                                  h                  ⁡                                      (                    n                    )                                                  ⁢                                  cos                  ⁡                                      (                                                                                            π                          ⁡                                                      (                                                                                          2                                ⁢                                k                                                            +                              1                                                        )                                                                          ⁢                                                  (                                                                                    2                              ⁢                              n                                                        +                                                          N                              /                              2                                                        +                            1                                                    )                                                                                            2                        ⁢                        N                                                              )                                                                                      ,                                  ⁢                              for            ⁢                                                  ⁢            0                    ≤          k          ≤                                    N              2                        -            1                                              (        1        )            where x0 represents the MDCT input signal, N represents the block length, h represents the window function for forward transform, y0 represents the MDCT output signal, C0 represents a constant, n represents an integer between 0 and N−1 and k represents an integer between 0 and N/2−1. Since the MDCT processing operation is conducted on a block by block basis for the cut out time series data so as to separate each block, the block number J is omitted from the above formula. Additionally, since the value of C0 essentially does not affect the method used for the MDCT, C0=1 is assumed here for the sake of convenience.
When carrying out computations with the above formula, firstly window for forward transform is applied to x0 to obtain x01 as expressed by formula (2) below.x01(n)=x0(n)h(n), for 0≦n≦N−1  (2)
Then, x02 is obtained from x01 that is obtained by using formula (2) above by using formula (3) below.
                                          x            02                    ⁡                      (            n            )                          =                  {                                                                                          -                                                                  x                        01                                            ⁡                                              (                                                  n                          +                                                                                    3                              ⁢                              N                                                        4                                                                          )                                                                              ,                                                                                                  for                    ⁢                                                                                  ⁢                    0                                    ≤                  n                  ≤                                                            N                      4                                        -                    1                                                                                                                                                                  x                      01                                        ⁡                                          (                                              n                        -                                                  N                          4                                                                    )                                                        ,                                                                                                  for                    ⁢                                                                                  ⁢                                          N                      4                                                        ≤                  n                  ≤                                      N                    -                    1                                                                                                          (        3        )            
Then, x03 is obtained by using formula (4) below.
                                                        x              03                        ⁡                          (              n              )                                =                                                    x                02                            ⁡                              (                                  2                  ⁢                  n                                )                                      -                                          x                02                            ⁡                              (                                  N                  -                  1                  -                                      2                    ⁢                    n                                                  )                                                    ,                                  ⁢                              for            ⁢                                                  ⁢            0                    ≤          n          ≤                                    N              2                        -            1                                              (        4        )            
Subsequently, a complex signal string Z01 is formed by using formula (5) below.
                                                        z              01                        ⁡                          (              n              )                                =                                    (                                                                    x                    03                                    ⁡                                      (                                          2                      ⁢                      n                                        )                                                  +                                  j                  ⁢                                                                          ⁢                                                            x                      03                                        ⁡                                          (                                                                        2                          ⁢                          n                                                +                        1                                            )                                                                                  )                        ⁢                          exp              ⁡                              (                                                      -                    j                                    ⁢                                                            2                      ⁢                      π                      ⁢                                                                                          ⁢                      n                                                              N                      /                      2                                                                      )                                                    ,                                  ⁢                              for            ⁢                                                  ⁢            0                    ≤          n          ≤                                    N              4                        -            1                                              (        5        )            
The obtained complex signal string Z01 is subjected to FFT on the basis of a length of N/4 to form a complex signal string Z02 as expressed by formula (6) below.
                                                        z              02                        ⁡                          (              k              )                                =                                    ∑                              n                =                0                                                              n                  /                  4                                -                1                                      ⁢                                                            z                  01                                ⁡                                  (                  n                  )                                            ⁢                              exp                ⁡                                  (                                                            -                      j                                        ⁢                                                                  2                        ⁢                        π                        ⁢                                                                                                  ⁢                        kn                                                                    N                        /                        4                                                                              )                                                                    ,                                  ⁢                              for            ⁢                                                  ⁢            0                    ≤          k          ≤                                    N              4                        -            1                                              (        6        )            
Then, from Z02 obtained in a manner as described above, four complex signal strings Z03, Z04, Z05 and Z06 are formed by using formulas (7) through (10) respectively.
                                                        z              03                        ⁡                          (              k              )                                =                                    1              2                        ⁢                          (                                                                    z                    02                                    ⁡                                      (                    k                    )                                                  +                                                      z                    02                    *                                    ⁡                                      (                                                                  N                        4                                            -                      1                      -                      k                                        )                                                              )                                      ,                              for            ⁢                                                  ⁢            0                    ≤          k          ≤                                    N              4                        -            1                                              (        7        )                                                                    z              04                        ⁡                          (              k              )                                =                                    1                              2                ⁢                j                                      ⁢                          exp              ⁡                              (                                                      -                    j                                    ⁢                                                            2                      ⁢                                                                                          ⁢                                              π                        ⁡                                                  (                                                                                    2                              ⁢                              k                                                        +                            1                                                    )                                                                                      N                                                  )                                      ⁢                          (                                                                    z                    02                                    ⁡                                      (                    k                    )                                                  -                                                      z                    02                    *                                    ⁡                                      (                                                                  N                        4                                            -                      1                      -                      k                                        )                                                              )                                      ,                                  ⁢                              for            ⁢                                                  ⁢            0                    ≤          k          ≤                                    N              4                        -            1                                              (        8        )                                                                    z              05                        ⁡                          (              k              )                                =                                    1              2                        ⁢                          (                                                                    z                    02                                    ⁡                                      (                                                                  N                        4                                            -                      1                      -                      k                                        )                                                  +                                                      z                    02                    *                                    ⁡                                      (                    k                    )                                                              )                                      ,                              for            ⁢                                                  ⁢            0                    ≤          k          ≤                                    N              4                        -            1                                              (        9        )                                                                    z              06                        ⁡                          (              k              )                                =                                    1                              2                ⁢                j                                      ⁢                          exp              ⁡                              (                                  j                  ⁢                                                            2                      ⁢                                                                                          ⁢                                              π                        ⁡                                                  (                                                                                    2                              ⁢                              k                                                        +                            1                                                    )                                                                                      N                                                  )                                      ⁢                          (                                                                    z                    02                                    ⁡                                      (                                                                  N                        4                                            -                      1                      -                      k                                        )                                                  -                                                      z                    02                    *                                    ⁡                                      (                    k                    )                                                              )                                      ,                                  ⁢                              for            ⁢                                                  ⁢            0                    ≤          k          ≤                                    N              4                        -            1                                              (        10        )            
Thereafter, y01(k) is obtained for a range between 0 and N/2−1 from the above complex signal strings Z03, Z04, Z05 and Z06 by using formula (11) below.
                                          y            01                    ⁡                      (            k            )                          =                  Re          (                                                    exp                ⁡                                  (                                                            -                      j                                        ⁢                                                                  2                        ⁢                                                  π                          ⁡                                                      (                                                                                          2                                ⁢                                k                                                            +                              1                                                        )                                                                                                                      4                        ⁢                        N                                                                              )                                            ⁢                              (                                                                            z                      03                                        ⁡                                          (                      k                      )                                                        +                                                            z                      04                                        ⁡                                          (                      k                      )                                                                      )                            ⁢                                                          ⁢                                                                                                                                            y                          01                                                ⁡                                                  (                                                                                    N                              /                              2                                                        -                            1                            -                            k                                                    )                                                                    =                                            ⁢                                              Re                        (                                                                              -                            j                                                    ⁢                                                                                                          ⁢                                                      exp                            ⁡                                                          (                                                              j                                ⁢                                                                                                      2                                    ⁢                                                                          π                                      ⁡                                                                              (                                                                                                                              2                                            ⁢                                            k                                                                                    +                                          1                                                                                )                                                                                                                                                                                  4                                    ⁢                                    N                                                                                                                              )                                                                                                                                                                                                                                                                                      ⁢                                                  (                                                                                                                    z                                05                                                            ⁢                                                              (                                k                                )                                                                                      +                                                                                          z                                06                                                            ⁡                                                              (                                k                                )                                                                                                              )                                                )                                            ,                                                                                  ⁢                                                          ⁢              for              ⁢                                                          ⁢              0                        ≤            k            ≤                                          N                4                            -              1                                                          (        11        )            
As proved in Japanese Patent Application Laid-Open No. 5-183442, this agree with y0 defined by formula (1).
Meanwhile, the IMDCT defining equation is given by formula (12) below.
                                                        x              1                        ⁡                          (              n              )                                =                                    C              1                        ⁢                          f              ⁡                              (                n                )                                      ⁢                                          ∑                                  k                  =                  0                                                                      N                    /                    2                                    -                  1                                            ⁢                                                                    y                    1                                    ⁡                                      (                    k                    )                                                  ⁢                                  cos                  ⁡                                      (                                                                                            π                          ⁡                                                      (                                                                                          2                                ⁢                                k                                                            +                              1                                                        )                                                                          ⁢                                                  (                                                                                    2                              ⁢                              n                                                        +                                                          N                              /                              2                                                        +                            1                                                    )                                                                                            2                        ⁢                        N                                                              )                                                                                      ,                                  ⁢                              for            ⁢                                                  ⁢            0                    ≤          n          ≤                      N            -            1                                              (        12        )            where y1 represents the IMDCT input signal, N represents the block length, f represents the window function for inverse transform, x1 represents the IMDCT output signal, C1 represents a constant, n represents an integer between 0 and N−1 and k represents an integer between 0 and N/2−1. Since the IMDCT processing operation is conducted on a block by block basis for the cut out time series data so as to separate each block, the block number J is omitted from the above formula. Additionally, since the value of C1 essentially does not affect the method used for the IMDCT, C1=1 is assumed here for the sake of convenience.
When carrying out computations with the above formula, firstly y1 is rearranged to form y11 by means of formula (13) below.
                                          y            11                    ⁡                      (            k            )                          =                  {                                                                                                                y                      1                                        ⁡                                          (                                              2                        ⁢                        k                                            )                                                        ,                                                                                                  for                    ⁢                                                                                  ⁢                    0                                    ≤                  k                  ≤                                                            N                      4                                        -                    2                                                                                                                                            -                                                                  y                        1                                            ⁡                                              (                                                  N                          -                          1                          -                                                      2                            ⁢                            k                                                                          )                                                                              ,                                                                                                  for                    ⁢                                                                                  ⁢                                          N                      4                                                        ≤                  k                  ≤                                                            N                      2                                        -                    1                                                                                                          (        13        )            
Subsequently, a complex signal string z11 having a length of N/4 is formed by using formula (14) below from y11.
                                                        z              11                        ⁡                          (              k              )                                =                                    (                                                                    y                    11                                    ⁡                                      (                                          2                      ⁢                      k                                        )                                                  +                                  j                  ⁢                                                                          ⁢                                                            y                      11                                        ⁡                                          (                                                                        2                          ⁢                          k                                                +                        1                                            )                                                                                  )                        ⁢                          exp              ⁡                              (                                                      -                    j                                    ⁢                                                            2                      ⁢                      π                      ⁢                                                                                          ⁢                      k                                                              (                                              N                        /                        2                                            )                                                                      )                                                    ,                                  ⁢                              for            ⁢                                                  ⁢            0                    ≤          k          ≤                                    N              4                        -            1                                              (        14        )            
The obtained complex signal string z11 is subjected to FFT on the basis of a length of N/4 to form a complex signal string Z12 as expressed by formula (15) below.
                                                        z              12                        ⁡                          (              n              )                                =                                    ∑                              k                =                0                                                              n                  /                  4                                -                1                                      ⁢                                                            z                  11                                ⁡                                  (                  k                  )                                            ⁢                              exp                ⁡                                  (                                                            -                      j                                        ⁢                                                                  2                        ⁢                        π                        ⁢                                                                                                  ⁢                        nk                                                                    (                                                  N                          /                          4                                                )                                                                              )                                                                    ,                              for            ⁢                                                  ⁢            0                    ≤          n          ≤                                    N              4                        -            1                                              (        15        )            
Then, from z12 obtained in a manner as described above, four complex signal strings z13, z14, z15 and z16 are formed by using formulas (16) through, (19) below respectively.
                                                        z              13                        ⁡                          (              n              )                                =                                    1              2                        ⁢                          (                                                                    z                    12                                    ⁡                                      (                    n                    )                                                  +                                                      z                    12                    *                                    ⁡                                      (                                                                  N                        4                                            -                      1                      -                      n                                        )                                                              )                                      ,                              for            ⁢                                                  ⁢            0                    ≤          n          ≤                                    N              4                        -            1                                              (        16        )                                                                    z              14                        ⁡                          (              n              )                                =                                    1                              2                ⁢                j                                      ⁢                          exp              ⁡                              (                                                      -                    j                                    ⁢                                                            2                      ⁢                                                                                          ⁢                                              π                        ⁡                                                  (                                                                                    2                              ⁢                              n                                                        +                            1                                                    )                                                                                      N                                                  )                                      ⁢                          (                                                                    z                    12                                    ⁡                                      (                    n                    )                                                  -                                                      z                    12                    *                                    ⁡                                      (                                                                  N                        4                                            -                      1                      -                      n                                        )                                                              )                                      ,                                  ⁢                              for            ⁢                                                  ⁢            0                    ≤          n          ≤                                    N              4                        -            1                                              (        17        )                                                                    z              15                        ⁡                          (              n              )                                =                                    1              2                        ⁢                          (                                                                    z                    12                                    ⁡                                      (                                                                  N                        4                                            -                      1                      -                      n                                        )                                                  +                                                      z                    12                    *                                    ⁡                                      (                    n                    )                                                              )                                      ,                              for            ⁢                                                  ⁢            0                    ≤          n          ≤                                    N              4                        -            1                                              (        18        )                                                                    z              16                        ⁡                          (              n              )                                =                                    1                              2                ⁢                j                                      ⁢                          exp              ⁡                              (                                  j                  ⁢                                                            2                      ⁢                                              π                        ⁡                                                  (                                                                                    2                              ⁢                              n                                                        +                            1                                                    )                                                                                      N                                                  )                                      ⁢                          (                                                                    z                    12                                    ⁡                                      (                                                                  N                        4                                            -                      1                      -                      n                                        )                                                  -                                                      z                    12                    *                                    ⁡                                      (                    n                    )                                                              )                                      ,                                  ⁢                              for            ⁢                                                  ⁢            0                    ≤          n          ≤                                    N              4                        -            1                                              (        19        )            
Thereafter, x11(n) is obtained for a range between 0 and N/2−1 from the above complex signal strings z13, z14, z15 and z16 by using formula (20) below.
                                                        x              11                        ⁡                          (              n              )                                =                      Re            ⁡                          (                                                exp                  ⁡                                      (                                                                  -                        j                                            ⁢                                                                        2                          ⁢                                                      π                            ⁡                                                          (                                                                                                2                                  ⁢                                  n                                                                +                                1                                                            )                                                                                                      N                                                              )                                                  ⁢                                  (                                                                                    z                        13                                            ⁡                                              (                        n                        )                                                              +                                                                  z                        14                                            ⁡                                              (                        n                        )                                                                              )                                            )                                      ⁢                                  ⁢                                                            x                11                            ⁡                              (                                                      N                    2                                    -                  1                  -                  n                                )                                      =                          Re              ⁡                              (                                                      -                    j                                    ⁢                                                                          ⁢                                      exp                    ⁡                                          (                                              j                        ⁢                                                                              2                            ⁢                                                          π                              ⁡                                                              (                                                                                                      2                                    ⁢                                    n                                                                    +                                  1                                                                )                                                                                                              N                                                                    )                                                        ⁢                                      (                                                                                            z                          15                                                ⁡                                                  (                          n                          )                                                                    +                                                                        z                          16                                                ⁡                                                  (                          n                          )                                                                                      )                                                  )                                              ,                                          ⁢                                    for              ⁢                                                          ⁢              0                        ≤            n            ≤                                          N                4                            -              1                                                          (        20        )            
The obtained x11 is then subjected to a rearrangement, changing the polarity thereof, and a window for inverse transform is applied thereto to obtain x12 as expressed by formula (21) below.
                                          x            12                    ⁡                      (            n            )                          =                  {                                                                                                                f                      ⁡                                              (                        n                        )                                                              ⁢                                                                  x                        11                                            ⁡                                              (                                                  n                          +                                                      N                            4                                                                          )                                                                              ,                                                                                                  for                    ⁢                                                                                  ⁢                    0                                    ≤                  n                  ≤                                                            N                      4                                        -                    1                                                                                                                                                                  -                                              f                        ⁡                                                  (                          n                          )                                                                                      ⁢                                                                  x                        11                                            ⁡                                              (                                                                                                            3                              ⁢                              N                                                        4                                                    -                          1                          -                          n                                                )                                                                              ,                                                                                                  for                    ⁢                                                                                  ⁢                                          N                      4                                                        ≤                  n                  ≤                                                                                    3                        ⁢                        N                                            4                                        -                    1                                                                                                                                                                  -                                              f                        ⁡                                                  (                          n                          )                                                                                      ⁢                                                                  x                        11                                            ⁡                                              (                                                  n                          -                                                                                    3                              ⁢                              N                                                        4                                                                          )                                                                              ,                                                                                                  for                    ⁢                                                                                  ⁢                                                                  3                        ⁢                        N                                            4                                                        ≤                  n                  ≤                                      N                    -                    1                                                                                                          (        21        )            
As proved in Japanese Patent Application Laid-Open No. 5-183442, this agree with x1 defined by formula (12).
As described above, a linear forward transform for the forward transform computations of MDCT to be conducted on the N samples of the input signal can be realized by means of computations for performing an FFT on a complex signal with a length of N/4. Thus, the volume of computations or the work area for computations can be reduced. On the other hand, a linear inverse transform for inverse transform computations of MDCT to be conducted on the N/2 independent spectrum input signal can be realized by means of computations for performing an FFT on a complex signal with a length of N/4. Thus, the volume of computations or the work area for computations can be reduced.
However, in a device for high efficiency coding/decoding using MDCT and IMDCT, there may be cases where it is desirable to reduce the volume of computations by limiting the frequency band required for decoding particularly when the processing capacity of the device is small.
FIGS. 2A and 2B shows the MDCT and the IMDCT when the frequency band is limited.
Referring to FIG. 2A, when the samples Ta obtained by removing samples Tb to decimate a block of N samples are subjected to an MDCT, N/2 spectrums indicated by Sa and Sb in FIG. 2A are obtained. Furthermore, when the N/4 spectrums of lower order indicated by Sa in FIG. 2A are selected from the above spectrums and subjected to an IMDCT, the sampling frequency is doubled and a time series signal of N/2 samples is obtained.
Thus, the volume of arithmetic operations of FFT is a half of the comparable volume that is required when the frequency band is not limited.
Similarly, as shown in FIG. 2B, when the N/8 spectrums of lower order are selected from the above spectrums and subjected to an IMDCT, the sampling frequency is quadrupled and a time series signal of N/4 samples is obtained. Thus, the volume of arithmetic operations of FFT is a quarter of the comparable volume that is required when the frequency is not limited.
Now, N signals are decimated to produce N/(2^m) signals and a window is applied thereto to obtain X01 by using formula (22) below.
                                                        X              01                        ⁡                          (              n              )                                =                                    h              ⁡                              (                                  2                  n                  m                                )                                      ⁢                                          x                0                            ⁡                              (                                  2                  n                  m                                )                                                    ,                              for            ⁢                                                  ⁢            0                    ≤          n          ≤                                    N                              2                m                                      -            1                                              (        22        )            
Then, the MDCT is expressed by formula (23) below.
                                                                        Y                01                            ⁡                              (                k                )                                      =                                          ∑                                  n                  =                  0                                                                      N                    /                                          2                      m                                                        -                  1                                            ⁢                                                                    X                    01                                    ⁡                                      (                    n                    )                                                  ⁢                                  cos                  ⁡                                      (                                                                                            π                          ⁡                                                      (                                                                                          2                                ⁢                                k                                                            +                              1                                                        )                                                                          ⁢                                                  (                                                                                                                    2                                                                  m                                  +                                  1                                                                                            ⁢                              n                                                        +                                                          N                              /                              2                                                        +                            1                                                    )                                                                                            2                        ⁢                        N                                                              )                                                                                ;                ⁢                                  ⁢                              for            ⁢                                                  ⁢            0                    ≤          k          ≤                                    N                              2                                  m                  +                  1                                                      -            1                                              (        23        )            
Subsequently, X01 is rearranged by using formula (24) below to form X02 in a manner as described in Japanese Patent Application Laid-Open No. 5-183442.
                                          X            02                    ⁡                      (            n            )                          =                  {                                                                                          -                                                                  X                        01                                            ⁡                                              (                                                  n                          +                                                                                    3                              ⁢                              N                                                                                      2                                                              m                                +                                2                                                                                                                                    )                                                                              ,                                                                                                  for                    ⁢                                                                                  ⁢                    0                                    ≤                  n                  ≤                                                            N                                              2                                                  m                          +                          2                                                                                      -                    1                                                                                                                                                                  X                      01                                        ⁡                                          (                                              n                        -                                                  N                                                      2                                                          m                              +                              2                                                                                                                          )                                                        ,                                                                                                  for                    ⁢                                                                                  ⁢                                          N                                              2                                                  m                          +                          2                                                                                                      ≤                  n                  ≤                                                            N                                              2                        m                                                              -                    1                                                                                                          (        24        )            
Formula (25) below is obtained, using X02 in a manner as described in Japanese Patent Application Laid-Open No.5-183442.
                                                                                          Y                  01                                ⁡                                  (                  k                  )                                            =                            ⁢                                                ∑                                      n                    =                    0                                                                              N                      /                                              2                        m                                                              -                    1                                                  ⁢                                                                            X                      02                                        ⁡                                          (                      n                      )                                                        ⁢                                      cos                    ⁡                                          (                                                                                                    π                            ⁡                                                          (                                                                                                2                                  ⁢                                  k                                                                +                                1                                                            )                                                                                ⁢                                                      (                                                                                                                            2                                                                      m                                    +                                    1                                                                                                  ⁢                                n                                                            +                              1                                                        )                                                                                                    2                          ⁢                          N                                                                    )                                                                                                                                              =                            ⁢                                                ∑                                      n                    =                    0                                                                              N                      /                                              2                                                  m                          +                          1                                                                                      -                    1                                                  ⁢                                                                            X                      0                                        ⁡                                          (                                              2                        ⁢                        n                                            )                                                        ⁢                  cos                                                                                                                      ⁢                                                (                                                                                    π                        ⁡                                                  (                                                                                    2                              ⁢                              k                                                        +                            1                                                    )                                                                    ⁢                                              (                                                                                                            2                                                              m                                +                                2                                                                                      ⁢                            n                                                    +                          1                                                )                                                                                    2                      ⁢                      N                                                        )                                +                                                      ∑                                          n                      =                      0                                                                                      N                        /                                                  2                                                      m                            +                            1                                                                                              -                      1                                                        ⁢                                      X                    02                                                                                                                                        ⁢                                                (                                                            2                      ⁢                      n                                        +                    1                                    )                                ⁢                                  cos                  ⁡                                      (                                                                                            π                          ⁡                                                      (                                                                                          2                                ⁢                                k                                                            +                              1                                                        )                                                                          ⁢                                                  (                                                                                                                    2                                                                  m                                  +                                  1                                                                                            ⁢                                                              (                                                                                                      2                                    ⁢                                    n                                                                    +                                  1                                                                )                                                                                      +                            1                                                    )                                                                                            2                        ⁢                        N                                                              )                                                                                                                          =                            ⁢                                                ∑                                      n                    =                    0                                                                              N                      /                                              2                                                  m                          +                          1                                                                                      -                    1                                                  ⁢                                                                            X                      02                                        ⁡                                          (                                              2                        ⁢                        n                                            )                                                        ⁢                  cos                                                                                                                      ⁢                                                (                                                                                    π                        ⁡                                                  (                                                                                    2                              ⁢                              k                                                        +                            1                                                    )                                                                    ⁢                                              (                                                                                                            2                                                              m                                +                                2                                                                                      ⁢                            n                                                    +                          1                                                )                                                                                    2                      ⁢                      N                                                        )                                -                                  ∑                                      n                    =                    0                                                                              N                      /                                              2                                                  m                          +                          1                                                                                      -                    1                                                                                                                                        ⁢                                                                    X                    02                                    ⁡                                      (                                                                  N                                                  2                          m                                                                    -                                              2                        ⁢                        n                                            -                      1                                        )                                                  ⁢                cos                                                                                                      ⁢                              (                                                                            π                      ⁡                                              (                                                                              2                            ⁢                            k                                                    +                          1                                                )                                                              ⁢                                          (                                                                                                    -                                                          2                                                              m                                +                                2                                                                                                              ⁢                          n                                                -                                                  2                                                      m                            +                            1                                                                          +                        1                                            )                                                                            2                    ⁢                    N                                                  )                                                                                        =                            ⁢                              Re                ⁢                                  {                                                            ∑                                              n                        =                        0                                                                                              N                          /                                                      2                                                          m                              +                              1                                                                                                      -                        1                                                              ⁢                                          (                                                                                                    X                            02                                                    ⁡                                                      (                                                          2                              ⁢                              n                                                        )                                                                          ⁢                        exp                                                                                                                                                                                                    ⁢                                  (                                                            -                      j                                        ⁢                                                                  π                        ⁡                                                  (                                                                                    2                              ⁢                              k                                                        +                            1                                                    )                                                                                            2                        ⁢                        N                                                                              )                                )                            -                                                X                  02                                ⁡                                  (                                                            N                                              2                        m                                                              -                                          2                      ⁢                      n                                        -                    1                                    )                                                                                                                      ⁢                                                exp                  ⁡                                      (                                                                  -                        j                                            ⁢                                                                                                    π                            ⁡                                                          (                                                                                                2                                  ⁢                                  k                                                                +                                1                                                            )                                                                                ⁢                                                      (                                                                                          2                                                                  m                                  +                                  1                                                                                            -                              1                                                        )                                                                                                    2                          ⁢                          N                                                                                      )                                                  ⁢                exp                                                                                                                        ⁢                                  (                                                            -                      j                                        ⁢                                                                                            π                          ⁡                                                      (                                                                                          2                                ⁢                                k                                                            +                              1                                                        )                                                                          ⁢                        n                                                                    N                        /                                                  2                                                      m                            +                            1                                                                                                                                )                                }                            ,                                                          ⁢                                                for                  ⁢                                                                          ⁢                  0                                ≤                n                ≤                                                      N                                          2                                              m                        +                        1                                                                              -                  1                                                                                        (        25        )            
If Z01 is expressed by formula (26) below, it then can also be expressed by formula (27).
                                                                                                              Z                    01                                    ⁡                                      (                    n                    )                                                  =                                ⁢                                                                                                    X                        02                                            ⁡                                              (                                                  2                          ⁢                          n                                                )                                                              ⁢                                          exp                      ⁡                                              (                                                                              -                            j                                                    ⁢                                                                                    π                              ⁡                                                              (                                                                                                      2                                    ⁢                                    k                                                                    +                                  1                                                                )                                                                                                                    2                              ⁢                              N                                                                                                      )                                                                              -                                                            X                      02                                        ⁡                                          (                                                                        N                          /                                                      2                            m                                                                          -                        1                        -                                                  2                          ⁢                          n                                                                    )                                                                                                                                                              ⁢                                                      exp                    ⁡                                          (                                                                        -                          j                                                ⁢                                                                                                            π                              ⁡                                                              (                                                                                                      2                                    ⁢                                    k                                                                    +                                  1                                                                )                                                                                      ⁢                                                          (                                                                                                2                                                                      m                                    +                                    1                                                                                                  -                                1                                                            )                                                                                                            2                            ⁢                            N                                                                                              )                                                        ,                                                                    ⁢                                  ⁢                              for            ⁢                                                  ⁢            0                    ≤          n          ≤                                    N                              2                                  m                  +                  1                                                      -            1                                              (        26        )                                                                    Z              02                        ⁡                          (              n              )                                =                      Re            ⁡                          (                                                ∑                                      n                    =                    0                                                                              N                      /                                              2                                                  m                          +                          1                                                                                      -                    1                                                  ⁢                                                                            z                      01                                        ⁡                                          (                      n                      )                                                        ⁢                                      exp                    ⁡                                          (                                                                        -                          j                                                ⁢                                                                                                            π                              ⁡                                                              (                                                                                                      2                                    ⁢                                    k                                                                    +                                  1                                                                )                                                                                      ⁢                            n                                                                                N                            /                                                          2                              m                                                                                                                          )                                                                                  )                                      ,                                  ⁢                              for            ⁢                                                  ⁢            0                    ≤          k          ≤                                    N                              2                                  m                  +                  1                                                      -            1                                              (        27        )            
However, since Z01 of the above instance is a complex number unlike the case of Japanese Patent Application Laid-Open No. 5-183442, there is not established a relationship where the sum and the difference of an even number and an odd number for n become complex conjugates. Then, as a result, it is not possible to perform computations for an FFT of the size of N/(2^(m+2)). In other words, the volume of arithmetic operations is similar to the comparable volume that is required when the frequency band is not limited in terms of number of multiplications and number of additions.